package com.shuang.stackAndQueue6;

import java.util.ArrayDeque;
import java.util.Deque;

public class MaxSlidingWindow {
    //自定义队列
    class MyQueue {

        Deque<Integer> deque = new ArrayDeque<>();

        //弹出元素方法
        //当要弹出的元素正好等于出口处元素时 将队列中的弹出 否则不做处理 (说明这个元素正好移除窗口外了 要将其弹出)
        //同时判断队列当前是否为空
        void poll(int val) {
            if (!deque.isEmpty() && val == deque.peek()) {
                deque.poll();
            }
        }

        //添加当前元素时 比较当前元素与队列入口处的值（队列后进来的值）大小
        // 如果小直接加进来即可 如果大则先将队列入口处的值弹出 再比较还大接着弹出
        // 当前元素小于前面的值时或者前面的数全部弹出了 将当前元素加进来（队列出口处的值最大）
        //为了保证队列元素单调递减
        //比如此时队列元素3,1，2将要入队，比1大，所以1弹出，此时队列：3,2
        void add(int val) {

            while (!deque.isEmpty() && val > deque.peekLast()) {
                deque.pollLast();
            }

            deque.offer(val);
        }

        //队列队顶元素始终为最大值
        int peek() {
            return deque.peek();
        }

    }

    public int[] maxSlidingWindow(int[] nums, int k) {

        //判断数组长度为一的话直接返回即可
        if (nums.length == 1) {
            return nums;
        }

        int len = nums.length - k + 1;
        //存放结果元素的数组
        int[] res = new int[len];
        //用于记录结果数组的索引下标
        int num = 0;

        //使用上述自定义队列
        MyQueue myQueue = new MyQueue();

        //先遍历数组前k个元素（第一个窗口）存到队列中
        for (int i = 0; i < k; i++) {
            myQueue.add(nums[i]);
        }
        //第一个窗口最大元素存到结果数组中
        res[num++] = myQueue.peek();

        //之后从数组第k+1个元素开始遍历 找到队列中要弹出的和要存的 将顶部元素添加到结果数组中
        for (int i = k; i < nums.length; i++) {
            //弹出操作 (窗口滑动引起的：要弹出的元素正好等于出口处元素时 将队列中的弹出 否则不做处理 (说明这个元素正好移除窗口外了 要将其弹出))
            myQueue.poll(nums[i - k]);

            //添加元素到队列中 （已实现保证队列元素单调递减）
            myQueue.add(nums[i]);

            //记录对应的最大值
            res[num++] = myQueue.peek();
        }

        return res;
    }
}
